This invention relates to a router unit and a routing network for use as a transmission network in an electronic computer system.
An electronic computer system often has a plurality of processors and is put into operation as a multiprocessor system. Such a multiprocessor system is helpful to improve performance and throughput of the electronic computer system.
With the multiprocessor system, each processor partially takes charge of work to be processed and is operable in relation to the other processors. Data transmission is necessary between the processors through a transmission network arranged therebetween. The performance of the electronic computer system is therefore dependent on that of the transmission network.
A conventional transmission network is put into operation in a manner similar to a crossbar exchange system and is convenient because each processor can be connected through the transmission network to another processor. With an increase of the processors in number, the number of circuit elements necessary for the transmission network should inevitably be augmented in the order of N.sup.2 where N represents the number of the processors. The conventional transmission network therefore becomes expensive with the increase of the number N of the processors.
According to a technical paper contributed by Jack B. Dennis et al to SIGARCH Newsletter Volume 8, Number 3, pp. 1-8, for the seventh annual symposium held during May 6-8, 1980 under the title of "Building Blocks for Data Flow Prototypes," a routing network system is proposed as another conventional transmission system for transmitting each packet from an input port to an output port. Such a routing network comprises a plurality of router units arranged into a plurality of stages comprising a preceding stage and the succeeding stage following the preceding stage and therefore may be called a multistage network system. With the multistage network system, it is possible to accomplish performance equivalent to that of the crossbar exchange system. In addition, costs rise up only in the order of (N log N) even when the number N of the processors is increased. The multistage network system is therefore economical as compared with the before-described conventional routing network system.
However, conflicts or collisions unavoidably take place when a plurality of the processors concurrently transmit the packets to an identical processor through the multistage network system. The performance is seriously reduced on occurrence of the conflicts.
Furthermore, each router unit should be different in structure from the other router unit at every stage of the multistage network system because different operation must be carried out at every stage. In other words, each router unit is not interchangeable with one another.
It is preferable that each router unit of the succeeding stage can recognize each input port of the stage situated prior to the succeeding stage.